With the exponential growth of the Internet, Internet Protocol (IP) networks are growing at an amazing rate. Today's IP networks have complex network topologies, more protocols and variety of services. Managing IP networks has been harder than before, due to increased complexity in the configuration of the IP network elements. Configuration and maintenance of a large network needs several administrators. Communication among administrators is not always perfect. In large networks, it is very hard for administrators to keep track of existing configurations and to be consistent while reconfiguring networks.
Routers are critical network elements of IP networks, and the configuration of IP routers is a tedious and error prone task. The most important function of an IP router is to route data packets. A forwarding table inside a router is used to decide which route a packet should take to transit through the network. There are several ways to add entries to a forwarding table. Typically, a routing protocol builds this table dynamically. A “routing domain” is a collection of routers, and all routers in a routing domain run same routing protocol. One or more routing domains constitute an “autonomous system” (AS). A unique number, called the AS number, identifies each AS to the rest of the autonomous systems. Routing protocols designed to run among or between AS's are called “exterior gateway protocols” (EGP), while routing protocols designed to run inside an AS are called “interior gateway protocols (IGP). One of the most popular IGP is called the Open Shortest Path First (OSPF) protocol, and is described in “OSPF Version 2”, J. Moy, Internet Standard, April 1998, and in “OSPF Anatomy of an Internet Routing Protocol”, J. Moy, Addison-Wesley, 1998.
OSPF is a hierarchical routing protocol. It can run in an entire AS, which can be arbitrarily divided into OSPF “areas”. A unique number identifies these areas. An area identified by number zero is also called the OSPF “backbone”. A typical arrangement of a small portion of an autonomous system is illustrated in FIG. 1, which shows a group of interconnected routers R1 through R8 grouped into four areas designated Area 0 through Area 3. Area 0 is the backbone, since it contains transmission medium M. Areas 1 through 3 contain routers R1–R3, R4–R5, and R6–R8, respectively. Techniques for optimum grouping of routers in different areas is a network planning and design issue, which can be performed in a number of ways by persons skilled in the art.
In FIG. 1, a router is designated an “area border router” (ABR) if it is part of more than one area. Thus, routers R1, R4 and R6 are ABR's. Entries (i.e. routes) in a forwarding table are generally aggregated at the area level by the ABR'S, so that processing burden and storage requirements of the routers in the other areas are reduced. For OSPF to work correctly, at least one ABR in an area should be connected to the OSPF backbone M. This could be a physical or logical connection to a backbone. In FIG. 1, routers R1 and R4 are physically connected to backbone M. A logical connection is called a virtual link. When an administrator configures virtual link, (s)he makes an entry in configuration file of the routers on both ends specifying the router on the other end. In FIG. 1, router R6 has a virtual link VL to the backbone via router R4, the latter having a physical connection to backbone M.
A virtual link configuration can be handy in several cases. Two scenarios under which it is desirable to provide virtual links are as follows:
First, a virtual link is desirable to provide logical connectivity to a backbone when it is not feasible and/or justifiable to install a physical link. This might be the case when two separate networks are merging due to organizational merger. In FIG. 1, areas 1 and 2 could be a network owned by an organization A. Area 3 could be a network owned by another organization B. When organizations A and B merge, and thus desire to interconnect their previously separate networks, a virtual link VL could be used.
Second, a virtual link is also desirable to provide redundant backbone connectivity, such that at least two routers in an area are connected to the backbone. However, excessive redundancy is not desirable, either because it increases router load and network traffic. Persons skilled in the art have various methodologies available to determine an optimum number of virtual links for redundancy purposes.
An interesting phenomenon occurs when an administrator does not configure a virtual link between area 2 and area 3 in FIG. 1. Traffic between the routers in area 2 and area 3 (routers R4 through R8) can still flow, but the routers (R6 through R8) in area 3 will be disconnected from rest of the network. A virtual link between area 2 and are 3 gives full connectivity to routers R6–R8 in area 3. In all practical cases, full connectivity is desired.
In addition to the issue of creation of a virtual link when there is no physical connectivity between any router in an area and the backbone, another issue arises when it is desired to intentionally disable (for known reasons) the OSPF interface of a router. When this situation arises, the network administrator must take care to assure that undesired consequences do not occur. For example, disabling the OSPF interface on a particular router might disconnect one or more other OSPF areas, if virtual links are configured on that router, because disabling the OSPF interface disconnects all virtual links.
From above discussion, it can be seen that creation and management of virtual links in a network of routers using the OSPF protocol, is of vital importance. Traditionally, this task has been done manually, which often resulted in human errors due to oversight, lack of communication with peers, lack of network wide information and sometimes lack of knowledge.
One attempt to automate the process involving virtual links is described by Zhaohui Zhang, “Fixing Backbone Partition with Dynamic Virtual Links”, Internet draft, November 1995. Zhang proposes modification of the OSPF protocol implementation to dynamically configure Dynamic Virtual Links (DVL) when the backbone is partitioned. In accordance with Zhang's DVL approach, a virtual link is created dynamically by the OSPF protocol itself, upon detection of backbone partitioning. He also proposes to delete DVL when they are not needed.
Zhang's proposal has not been implemented in practice, because it would be difficult to deploy the technique in existing networks. Existing routers in these networks do not support DVL; all vendors would need to modify their OSPF implementation to interoperate with each other, and this would be nearly impossible to achieve in the real world. Accordingly, at the present time, there is no automated system for the creation and management of virtual links in a network of routers using the OSPF protocol, that can be easily implemented and deployed in the existing networks without software or hardware upgrade.